package bintree.leetcode;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/9/3 16:54
 * @Description:二叉树中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class Num94_InOrder {
    // 迭代法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> retList = new ArrayList<>();
        if (root == null)
            return retList;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            // 先向当前树向左一路走到底
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 此时左树走到底，弹出栈顶元素并访问
            cur = stack.pop();
            retList.add(cur.val);
            cur = cur.right;
        }
        return retList;
    }
//    // 递归法
//    public List<Integer> inorderTraversal(TreeNode root) {
//        // 终止条件
//        if (root == null)
//            return retList;
//        // 遍历左子树
//        inorderTraversal(root.left);
//        // 访问根节点
//        retList.add(root.val);
//        // 遍历右子树
//        inorderTraversal(root.right);
//        return retList;
//    }
}
